package Medium;

import java.util.Stack;

public class LC0735 {
    /**
     * 在小行星入栈时进行判断：如果栈顶元素和自己方向相同或者背离，则可以入栈；如果方向相反且栈顶元素更大，则销毁自身；如果自身更大，则销毁栈顶元素，
     * 重复之前的判断；如果大小相同，则销毁两颗行星。
     */
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            if (stack.empty()) stack.push(asteroid);
            else {
                boolean destroyFlag = false;
                while (!stack.empty() && stack.peek() > 0 && asteroid < 0) { // 会发生碰撞
                    int stackTop = stack.peek();
                    if (Math.abs(stackTop) == Math.abs(asteroid)) {
                        stack.pop();
                        destroyFlag = true;
                        break;
                    }
                    else if (Math.abs(asteroid) < Math.abs(stackTop)) {
                        destroyFlag = true;
                        break;
                    }
                    else { // 摧毁栈顶元素，重复循环
                        stack.pop();
                    }
                }
                if (!destroyFlag) stack.push(asteroid);
            }
        }

        int[] retArray = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            retArray[i] = stack.get(i);
        }
        return retArray;
    }
}
